#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

#define int ll

const int maxn = 310;
const int maxm = 100010;
const int maxv = 100000;

int n, m, q, dis[maxn][maxn], mn[maxn], ans[maxm];

struct MCMF {
  static const int N = 710;
  static const int M = 500010;
  int n, s, t, head[N], nxt[M << 1], to[M << 1], cost[M << 1], cap[M << 1];
  int from[N], dis[N], mn[N], tot, flow, sum;
  bool vis[N];
  void init() {
    memset(head, 0, sizeof(head));
    tot = 1, flow = 0, sum = 0;
  }
  void add_edge(int u, int v, int ca, int co) {
    to[++tot] = v, cap[tot] = ca, cost[tot] = co, nxt[tot] = head[u], head[u] = tot;
  }
  void add(int u, int v, int ca, int co) {
    add_edge(u, v, ca, co);
    add_edge(v, u, 0, -co);
  }
  bool spfa() {
    queue<int> q;
    rep(i, 1, n) dis[i] = 1e16;
    dis[s] = 0, mn[s] = 1e16, vis[s] = 1, q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop(), vis[u] = 0;
      for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i], ca = cap[i], co = cost[i];
        if (!ca) continue;
        if (dis[u] + co < dis[v]) {
          dis[v] = dis[u] + co;
          mn[v] = min(mn[u], ca);
          from[v] = i;
          if (!vis[v]) q.push(v), vis[v] = 1;
        }
      }
    }
    return dis[t] != 1e16;
  }
  void calc() {
    int x = t;
    flow += mn[t], sum += mn[t] * dis[t];
    while (x != s) {
      cap[from[x]] -= mn[t];
      cap[from[x] ^ 1] += mn[t];
      x = to[from[x] ^ 1];
    }
  }
  pll mcmf() {
    while (spfa()) calc(), ans[flow] = sum;
    return make_pair(flow, sum);
  }
} g;

signed main() {
  freopen("journey.in", "r", stdin);
  freopen("journey.out", "w", stdout);
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m >> q;
  rep (i, 1, n) rep (j, 1, n) dis[i][j] = 1e9;
  rep (i, 1, n) dis[i][i] = 0;
  rep (i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    chkmn(dis[u][v], w);
  }
  rep (k, 1, n) rep (i, 1, n) rep (j, 1, n) chkmn(dis[i][j], dis[i][k] + dis[k][j]);
  int s, t;
  g.init(), g.n = 2 * n + 2, g.s = s = 2 * n + 1, g.t = t = 2 * n + 2;
  rep (i, 1, n) g.add(s, i, 1, 0), g.add(i + n, t, 1, 0);
  rep (i, 1, n) rep (j, 1, n) if (i != j) g.add(i, j + n, 1, dis[i][j]);
  auto info = g.mcmf();
  while (q--) {
    int c, mn = 1e18;
    cin >> c;
    rep (i, 0, info.fi) chkmn(mn, c * (n - i) + ans[i]);
    cout << mn << '\n';
  }
}